Wireless mobile devices, including personal digital assistants (PDA's) and mobile phones, have a multitude of functions ranging from voice and data communications to Internet browsing. Data communications can include text messaging or email, while Internet browsing can include viewing news websites.
While many wireless mobile devices have voice communication capabilities, wireless text messaging and e-mail are becoming a preferred means of communication. Furthermore, users are constantly demanding the ability to browse the Internet wirelessly on their mobile devices. Hence, news media, entertainment listings, and virtually any content on the Internet should be viewable from the mobile device. Such rich content requires buffering, or storage, which is provided by the on-board memory, such as memory 22, in the mobile device.
Unfortunately, the consumer demand for minimally sized mobile devices constrains the amount of memory which can be included in a mobile device. For example, some mobile devices are limited to 16 MB of on-board memory, some of which may be allocated for running software applications, while the remaining portion is dedicated for storing data. Although modern personal computers (PC) can have 2 giga-bytes of dynamic memory, the high number of concurrent processes and applications run by the PC can quickly consume the available memory, and if inefficiently used, can degrade system performance.
Fortunately, text data in email messages, documents and web pages, can be compressed using lossless compression schemes in order to alleviate memory demand, and reduce transmission time of the data to and from a base station. One example of such text compression is the YK compression algorithm disclosed in U.S. Pat. No. 6,801,141 (Yang). Generally, the YK compression algorithm identifies longest prefix string matches in the document or page to be compressed, and replaces instances of repeating strings with a variable. The relative location of the variables are recorded, and storage of the compressed document can accordingly use less memory than the uncompressed document. The YK compression algorithm is but one compression scheme which can be used. Those skilled in the art will understand that there are different text compression algorithms which can be used.
Most applications, including compression schemes such as the YK compression algorithm, will need memory space to perform its functions. This memory can include static memory, transient memory and dynamic memory. Static memory allocation refers to the allocation of memory before the application is executed. Statically allocated memory provides high speed operation, but is generally restrictive, as the size of memory is fixed and unusable by other applications. Transient memory allocation refers to the allocation of memory for buffering information for a short duration of time. Transient memory is typically small, and does not significantly impact memory use relative to the static memory and the dynamic memory. Dynamic memory allocation refers to the allocation of memory while the application is running. Dynamic memory allocation is commonly used since applications will request and use specifically sized portions of memory for executing its functions. Of the listed types of allocated memory, dynamic memory allocation requires careful management to be effectively and efficiently used.
The following discussion herein relates solely to dynamic memory allocation. When memory is dynamically requested, the memory controller will first provide a specific portion of memory, such as a page, for use by the application. The application may then request one or more blocks within the page for storing data, where a block can be a predefined number of bytes or a specific number of requested bytes. When a block is requested by the application, the application will store a value corresponding to the actual size of the block in bytes. The purpose of storing this information is to allow the application to keep track of how much of the space within the allocated block is used up, so that it can request a larger memory block. as the need arises. In the YK compression algorithm for example, the data that needs to be stored can expand, eventually exceeding the capacity of the originally allocated memory block. In such a case, the allocated memory block can be released and a larger sized memory block can be allocated to the application in its place. If it is determined that the full capacity of the allocated memory block will never be used, then the allocated memory block can be released and a smaller memory block can be allocated in its place. Alternatively, the allocated memory block can be augmented by allocating one or more additional memory blocks to the application. FIG. 2 is a conceptual illustration of the typical data structure of a data block dynamically allocated to an application in a page of memory.
FIG. 2 shows a memory page 30 and two allocated blocks 32 and 34 within page 30. By example, the memory page 30 can be 64 k bytes in size. It is assumed in this example that addresses increase from the left side to the right side, and from the top to the bottom of page 30. When the application makes a request for memory having size “A”, the memory manager will first ensure that there sufficient room in the page, and then allocate a block having size “A”. A pointer, referred to as Pointer[1] for this first block, is returned to the application. Pointer[1] indicates the starting address of the block the application can use. If another request by the application is made for memory having size “B”, then a second block having size “B” is allocated, and Pointer[2] is returned to the application. Although the application requests memory having size “A” or “B”, additional information is appended to blocks 32 and 34 in the form of headers 36 and 38. Header's 36 and 38 include information regarding the size of the block it is appended to. This header can be 4 bytes long for example, and is considered overhead for the block. Hence, the data structure of an allocated memory has a payload portion for storing data, and a corresponding header portion.
The purpose of the header is now explained. When the application no longer needs either block 32 or 34 previously allocated to it, it will release the block and free it for later use. However, the memory manager must know the size of the block to be freed. Since the memory manager has the pointer to the beginning of the block to be freed, it will read the 4 preceding bytes of data to identify the size of the block. Therefore, the true size of the data block being used in the page 30 is the sum of the size of the requested payload space for storing data and the corresponding header. Accordingly, both the application and the memory manager will store a value corresponding to the size of the memory block. This data structure and general allocation scheme is ideally suited for applications where relatively large blocks of data are requested. For example, a typical application might request many blocks of memory each having a size of 128 bytes, therefore a 4 byte header represents approximately 3% overhead for the payload.
Unfortunately, this data structure is unsuitable for applications which request small blocks of memory, as will be further explained. A characteristic of the YK compression algorithm is the need to store many small blocks of data in a page of memory while executing its compression routine. A small block size can be between 6 bytes and 72 bytes for example. If a large proportion of blocks are 6 bytes in size for example, then a header 4 bytes in size accompanying the payload will contribute 40% overhead for the block. This means that a significant proportion of the page can be dedicated to storing header information, thereby reducing the effective memory available for storing actual data.
The general memory allocation scheme and examples described above assume that a page of memory is empty prior to allocation of memory blocks, which makes memory allocation straight-forward as the memory manager can progressively allocate sequential blocks of memory. An important feature of dynamic memory allocation is the ability to re-allocate freed blocks of memory within the page to one or more other applications. Unfortunately, there are inefficiencies in prior re-allocation schemes which add to the inefficiency of the header-based memory allocation scheme.
For example, the heap-based allocation scheme searches the memory for freed blocks of memory that are large enough to fit the requested block size. This scheme is processor intensive, and will negatively impact the performance of the system. The buddy block scheme maintains a linked list of free blocks, which can be memory intensive as the number of buddy blocks grows. The heap-based allocation scheme and the buddy block allocation scheme are well known in the art, and described in Fundamental Algorithms, Third Edition, Addison-Wesley, 1997, ISBN 0-201-89683-4, Section 2.4: Dynamic Storage Allocation, pp. 435-456, authored by Donald Knuth.
Another inefficiency in most general purpose memory allocation schemes is wasted space, also called internal fragmentation. For example, the buddy block allocation scheme typically manages blocks in sizes that are powers of two. So if the application requests an amount that is not an exact power of two, there is wasted space in the allocated block that will never be used.
Therefore, the available memory is quickly consumed when a large number of small memory blocks are allocated to one or more applications. This can be seen as low memory usage efficiency since a relatively high proportion of the memory may not be used to store application data.
Unfortunately, the application may cease to run if no further memory can be allocated to it. While more memory can be added to the mobile device to alleviate the high rate of memory consumption, the additional cost, increased size and increased power consumption of the device may not be acceptable to the end user.
It is, therefore, desirable to provide a method and system for increasing the memory usage efficiency when dynamically allocating small blocks of memory to one or more applications.